package com.github.yangyishe.p100;

import com.github.yangyishe.ListNode;

/**
 * 82. 删除排序链表中的重复元素 II
 * https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
 *
 * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,3,4,4,5]
 * 输出：[1,2,5]
 * 示例 2：
 *
 *
 * 输入：head = [1,1,1,2,3]
 * 输出：[2,3]
 *
 *
 * 提示：
 *
 * 链表中节点数目在范围 [0, 300] 内
 * -100 <= Node.val <= 100
 * 题目数据保证链表已经按升序 排列
 */
public class Problem82 {
    public static void main(String[] args) {
        ListNode instance = ListNode.getInstance(new int[]{1,1,1,2,3});

        Problem82 problem82 = new Problem82();
        ListNode result = problem82.deleteDuplicates(instance);
        result.print();
    }

    /**
     * 每次遍历时, 当前节点认为是一定不需要被删除的, 称为干净节点
     * 每次遍历内部, 先获取下一个节点的值, 标记为临时值. 内部深入遍历,
     * 如果再下个节点为空, 或节点值与临时值不一致, 则说明仅出现一次临时值, 跳出
     * 如果再下个节点不为空, 且节点值与临时值相等, 则说明临时值不是干净值, 找到下个不是临时值的节点或者Null, 将当前节点的下个节点设置为该值
     * 如果临时值不是干净值, 则外部遍历临时节点就不能深入, 而是继续考虑当前下一个节点是否是干净节点
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode root=new ListNode(-101);
        root.next=head;

        ListNode tempNode=root;
        ListNode innerTempNode;
        int tempVal;
        boolean isTempClean;
        while(tempNode.next!=null){
            tempVal=tempNode.next.val;
            isTempClean=true;
            innerTempNode=tempNode.next;
            while(innerTempNode.next!=null&&innerTempNode.next.val==tempVal){
                isTempClean=false;
                innerTempNode=innerTempNode.next;
            }
            if(!isTempClean){
                tempNode.next=innerTempNode.next;
            }

            if(isTempClean){
                tempNode=tempNode.next;
            }
        }

        return root.next;
    }
}

class DpListNode{

    int val;
    DpListNode next;
    DpListNode prev;

    public DpListNode() {
    }

    public DpListNode(int val) {
        this.val = val;
    }

    public void removeCurrent(){
        // 删除当前节点的前提, 是确定当前节点和当前节点的前一节点都不能为空. 这在方法内无法保证, 只能在方法外部保证
        prev.next=next;
        if(next!=null){
            next.prev=prev;
        }
    }

    public static DpListNode getInstance(ListNode listNode){
        if (listNode==null) {
            return null;
        }
        DpListNode dpListNode = new DpListNode(listNode.val);
        dpListNode.next=DpListNode.getInstance(listNode.next);
        if(listNode.next!=null){
            dpListNode.next.prev=dpListNode;
        }
        return dpListNode;
    }

    public ListNode toListNode(){
        ListNode listNode = new ListNode(this.val);
        if (this.next!=null) {
            listNode.next=this.next.toListNode();
        }
        return listNode;
    }
}